package com.promote.algorithm;

import com.promote.algorithm.ReverseList.ListNode;

import java.util.List;
import java.util.Random;
import java.util.Stack;

/**
 * @ClassName ReverseList
 * Description 翻转链表
 * @Author LiZiHao
 * Date 2021/8/23 9:59
 * @Version 1.0
 **/
public class ReverseList {

    /**
     * 使用栈解决
     * 栈先进后出
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        Stack<ListNode> stack = new Stack<>();

        //把链表节点全部放到栈中
        while (head != null) {
            stack.push(head);
            head = head.next;
        }
        if (stack.isEmpty()) {
            return null;
        }
        ListNode node = stack.pop();
        ListNode dumpy = node;

        //栈中的节点全部出栈，重新生成一个链表
        while (!stack.isEmpty()) {
            ListNode tempNode = stack.pop();
            node.next = tempNode;
            node = node.next;
        }
        node.next = null;

        return dumpy;
    }

    /**
     * 用双链表解决
     * 双链表求解是把原链表的结点一个个摘掉，每次摘掉的链表都让他成为新的链表的头结点，然后更新新链表
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        ListNode newHead = null;

        while (head != null) {
            ListNode temp = head.next;

            head.next = newHead;

            newHead = head;

            head = temp;
        }
        return newHead;
    }

    public ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;

        ListNode reverse = reverseList2(next);

        head.next.next = head;

        head.next = null;

        return reverse;
    }

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
}
